
public class BestSearchTree {
	int size = 7;
	double []p = {0.05, 0.4, 0.08, 0.04, 0.1, 0.1, 0.23};
	double minSearchTime = 0;
	double [][]A;
	
	double GetComputedSubResult(int start, int root, int end){
		double ret = 0;
		if(start <= root - 1)
		{
			ret += A[start][root-1];
		}
		
		if(root + 1 <= end)
		{
			ret += A[root + 1][end];
		}
		
		return ret;
	}
	
	double GetMinSubST(int start, int offset)
	{
		double ret = 0;
		for(int i = start; i <= start + offset; i++)
		{
			ret += p[i];
		}
		
		double min = 10000;
		for(int j = start; j <= start + offset; j++)
		{
			double t = GetComputedSubResult(start, j, start + offset);
			if(t < min)
				min = t;
		}
		
		ret += min;
		
		return ret;
	}
	
	
	public void PrintData(){
		for(int i = 0; i < size; i++)
		{
			for(int j = 0; j < size; j++)
				System.out.print(A[i][j] + "\t");
			
			System.out.print("\n");
		}
	}
	
	public void ComputeMinTime()
	{
		A = new double [7][7];
		for(int i = 0; i < size; i++)
		{
			for(int j = 0; j + i < size; j++)
			{
				A[j][j+i] = GetMinSubST(j, i);
			}
		}
	}
}
